package 代码题.动态规划题目;

/**
 * 动态规划问题的本质：穷举所有的情况，找状态转移方程。模拟人脑的操作，记录最值
 * <p>
 * 0-1背包问题
 */
public class DP_01 {

    /**
     * 有1个背包，重量为10，
     * 有5个物品，他们的价值和重量的键值对为
     * (1,5)(2,4)(3,3)(4,2)(5,1)
     * <p>
     * 背包能够装下并获得的最大价值为14。
     * 分别取物品(2,4)(3,3)(4,2)(5,1)
     * <p>
     * 状态转移方程：dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);
     * <p>
     * dp[i][j]表示的是在容量为j的情况下选取第i个物品的最大value值
     * 注意：第i个物品不是一定要全选。这里的选择是有顺序的
     * <p>
     * 本质是：穷举所有情况，找出状态转移方程
     *
     * @param args
     */
    public static void main(String[] args) {
        int[][] dp = new int[6][11];  //默认初始化二维数组为0.需要增加一个辅助行和辅助列
        int[] value = new int[]{0, 1, 2, 3, 4, 5};
        int[] weight = new int[]{0, 5, 4, 3, 2, 1};
        for (int i = 1; i < 6; i++) {
            for (int j = 1; j < 11; j++) {
                if (j - weight[i] >= 0) {
                    //当前物品可以放入背包，但是选不选是另外的事情
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
                } else {
                    dp[i][j] = dp[i - 1][j];
                }

            }
        }
        System.out.println(dp[5][10]);

        //打印最值得二维数组
        for (int i = 0; i < 6; i++) {
            for (int j = 0; j < 11; j++) {
                System.out.print(dp[i][j]+"\t");
            }
            System.out.println();
        }
    }
}
